<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8" >

<title>斐波那契数列的多种实现和性能 | 泥烟</title>

<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=no">

<link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.7.2/css/all.css" integrity="sha384-fnmOCqbTlWIlj8LyTjo7mOUStjsKC4pOpQbqyi7RrhN7udi9RwhKkMHpvLbHG9Sr" crossorigin="anonymous">
<link rel="shortcut icon" href="https://knight-02.gitee.io/favicon.ico?v=1715914391071">
<link rel="stylesheet" href="https://knight-02.gitee.io/styles/main.css">



<link rel="stylesheet" href="https://unpkg.com/aos@next/dist/aos.css" />
<script src="https://cdn.jsdelivr.net/npm/vue/dist/vue.js"></script>



    <meta name="description" content="[toc]
0. 普通斐波那契
import time
start = time.time()

def fib0(n: int) -&gt; int:
    if n &lt; 2:
        return n
    retur..." />
    <meta name="keywords" content="《算法精粹》" />
  </head>
  <body>
    <div id="app" class="main">

      <div class="sidebar" :class="{ 'full-height': menuVisible }">
  <div class="top-container" data-aos="fade-right">
    <div class="top-header-container">
      <a class="site-title-container" href="https://knight-02.gitee.io">
        <img src="https://knight-02.gitee.io/images/avatar.png?v=1715914391071" class="site-logo">
        <h1 class="site-title">泥烟</h1>
      </a>
      <div class="menu-btn" @click="menuVisible = !menuVisible">
        <div class="line"></div>
      </div>
    </div>
    <div>
      
        
          <a href="/" class="site-nav">
            首页
          </a>
        
      
        
          <a href="/archives" class="site-nav">
            归档
          </a>
        
      
        
          <a href="/tags" class="site-nav">
            标签
          </a>
        
      
        
          <a href="https://knight-02.gitee.io/post/knight02-first-blog-here-for-test" class="site-nav">
            关于
          </a>
        
      
        
          <a href="/links" class="site-nav">
            友链
          </a>
        
      
    </div>
  </div>
  <div class="bottom-container" data-aos="flip-up" data-aos-offset="0">
    <div class="social-container">
      
        
      
        
      
        
      
        
      
        
      
    </div>
    <div class="site-description">
      两岸猿声啼不住， 轻舟已过万重山
    </div>
    <div class="site-footer">
      Powered by <a href="https://github.com/getgridea/gridea" target="_blank">Gridea</a> | <a class="rss" href="https://knight-02.gitee.io/atom.xml" target="_blank">RSS</a>
    </div>
  </div>
</div>


      <div class="main-container">
        <div class="content-container" data-aos="fade-up">
          <div class="post-detail">
            <h2 class="post-title">斐波那契数列的多种实现和性能</h2>
            <div class="post-date">2023-12-27</div>
            
              <div class="feature-container" style="background-image: url('https://knight-02.gitee.io/post-images/fei-bo-na-qi-shu-lie-de-duo-chong-shi-xian-he-xing-neng.png')">
              </div>
            
            <div class="post-content" v-pre>
              <p>[toc]</p>
<h1 id="0-普通斐波那契">0. 普通斐波那契</h1>
<pre><code class="language-python">import time
start = time.time()

def fib0(n: int) -&gt; int:
    if n &lt; 2:
        return n
    return fib0(n-1) + fib0(n-2)

print(&quot;fib0(40) = &quot;, fib0(40))
end = time.time()
print('程序运行时间为: %s Seconds' % (end-start))
</code></pre>
<blockquote>
<p>fib0(40) =  102334155<br>
程序运行时间为: 29.292827367782593 Seconds</p>
</blockquote>
<figure data-type="image" tabindex="1"><img src="https://knight-02.gitee.io/post-images/2138326-20230115154707557-1166377612.png" alt="" loading="lazy"></figure>
<h1 id="1-结果缓存">1. 结果缓存</h1>
<blockquote>
<p>每次计算任务完成后就把结果保存起来，这样在下次需要时即可直接检索出结果，而不需要一而再再而三地重复计算</p>
</blockquote>
<pre><code class="language-python">from typing import Dict
import time
start = time.time()
memo: Dict[int, int] = {0: 0, 1: 1}

def fib1(n: int) -&gt; int:
    if n not in memo:
        memo[n] = fib1(n-1) + fib1(n-2)
    return memo[n]

print(&quot;fib1(120) = &quot;, fib1(120))
end = time.time()
print('程序运行时间为: %s Seconds' % (end-start))
</code></pre>
<blockquote>
<p>fib1(120) =  5358359254990966640871840<br>
程序运行时间为: 0.005672931671142578 Seconds<br>
fib1(120) =  5358359254990966640871840<br>
程序运行时间为: 0.00408172607421875 Seconds<br>
fib1(120) =  5358359254990966640871840<br>
程序运行时间为: 0.004380702972412109 Seconds</p>
</blockquote>
<h1 id="2-自动化结果缓存">2. 自动化结果缓存</h1>
<blockquote>
<ul>
<li>每次用新的参数执行fib()时，该装饰器就会把返回值缓存起来。以后再用相同的参数调用fib()时，都会从缓存中读取该参数对应的fib()之前的返回值并返回</li>
<li>@lru_cache的maxsize属性表示对所装饰的函数最多应该缓存多少次最近的调用结果，如果将其设置为None就表示没有限制<br>
<a href="https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU)">Cache replacement policies</a><br>
<img src="https://knight-02.gitee.io/post-images/2138326-20230115155305772-536945396.png" alt="" loading="lazy"><br>
<img src="https://knight-02.gitee.io/post-images/2138326-20230115163908950-559953534.png" alt="" loading="lazy"></li>
</ul>
</blockquote>
<pre><code class="language-python">from functools import lru_cache
import time
start = time.time()

@lru_cache(maxsize=None)
def fib2(n: int) -&gt; int:
    if n &lt; 2:
        return n
    return fib2(n-1) + fib2(n-2)

print(&quot;fib2(120) = &quot;, fib2(120))
end = time.time()
print('程序运行时间为: %s Seconds' % (end-start))
</code></pre>
<blockquote>
<p>fib2(120) =  5358359254990966640871840<br>
程序运行时间为: 6.771087646484375e-05 Seconds<br>
fib2(120) =  5358359254990966640871840<br>
程序运行时间为: 7.05718994140625e-05 Seconds<br>
fib2(120) =  5358359254990966640871840<br>
程序运行时间为: 7.677078247070312e-05 Seconds</p>
</blockquote>
<h1 id="3-迭代">3. 迭代</h1>
<pre><code class="language-python">import time
start = time.time()

def fib3(n: int) -&gt; int:
    if n == 0: return 0
    last: int = 0
    next: int = 1
    for _ in range(1, n):
        last, next = next, last+next
    return next

print(&quot;fib3(120) = &quot;, fib3(120))
end = time.time()
print('程序运行时间为: %s Seconds' % (end-start))
</code></pre>
<blockquote>
<p>fib3(120) =  5358359254990966640871840<br>
程序运行时间为: 1.5020370483398438e-05 Seconds<br>
fib3(120) =  5358359254990966640871840<br>
程序运行时间为: 1.33514404296875e-05 Seconds<br>
fib3(120) =  5358359254990966640871840<br>
程序运行时间为: 1.430511474609375e-05 Seconds</p>
</blockquote>
<h1 id="4-生成器">4. 生成器</h1>
<blockquote>
<p>目前为止，已完成的这些函数都只能输出斐波那契序列中的单个值。如果要将到某个值之前的整个序列输出，又该怎么做呢？用yield语句很容易就能把fib5()转换为Python生成器。在对生成器进行迭代时，每轮迭代都会用yield语句从斐波那契序列中吐出一个值</p>
</blockquote>
<pre><code class="language-python">from typing import Generator
import time
start = time.time()

def fib4(n: int) -&gt; Generator[int, None, None]:
    yield 0
    if n &gt; 0: yield 1
    last: int = 0
    next: int = 1
    for _ in range(1, n):
        last, next = next, last+next
        yield next

res = [_ for _ in fib4(120)]
print(&quot;fib4(120) = &quot;, res[120])
end = time.time()
print('程序运行时间为: %s Seconds' % (end-start))
</code></pre>
<blockquote>
<p>fib4(120) =  5358359254990966640871840<br>
程序运行时间为: 0.004061222076416016 Seconds<br>
fib4(120) =  5358359254990966640871840<br>
程序运行时间为: 0.004450798034667969 Seconds<br>
fib4(120) =  5358359254990966640871840<br>
程序运行时间为: 0.004158735275268555 Seconds</p>
</blockquote>

            </div>
            
              <div class="tag-container">
                
                  <a href="https://knight-02.gitee.io/tag/K-Wc1B22o/" class="tag">
                    《算法精粹》
                  </a>
                
              </div>
            
            
              <div class="next-post">
                <div class="next">下一篇</div>
                <a href="https://knight-02.gitee.io/post/games101-huan-jing-pei-zhi-ji-lu-wslubuntu2204vscodevcxsrv/">
                  <h3 class="post-title">
                    GAMES101环境配置记录 wsl+ubuntu22.04+vscode+VcXsrv
                  </h3>
                </a>
              </div>
            

            

          </div>

        </div>
      </div>
    </div>

    <script src="https://unpkg.com/aos@next/dist/aos.js"></script>
<script type="application/javascript">

AOS.init();

var app = new Vue({
  el: '#app',
  data: {
    menuVisible: false,
  },
})

</script>


  <script src="//cdn.jsdelivr.net/gh/highlightjs/cdn-release@11.5.1/build/highlight.min.js"></script>
  <script>
    hljs.initHighlightingOnLoad()
  </script>





  </body>
</html>
